/*********************************************************************************
  *Copyright (c)    2021   xldeng
  *FileName:        295b.cpp.c
  *Author:          xldeng
  *Version:         1.0
  *Date:            2021/2/18 9:07
  *Description:     
  *Others:          
  *Function List:   
     1.…………
  *History:  
     1.Date:
       Author:
       Modification:
**********************************************************************************/
#include "../header.h"

class MedianFinder {
    multiset<int> data;
    multiset<int>::iterator lo, hi;
public:
    /** initialize your data structure here. */
    MedianFinder() : lo(data.end()), hi(data.end()) {}

    void addNum(int num) {
        const int n = data.size();
        data.insert(num);
        if (n == 0)
            lo = hi = data.begin();
        else if (n & 1)
            if (num < *lo)
                lo--;
            else
                hi++;
        else if (num > *lo && num < *hi) {
            lo++;
            hi--;
        } else if (num >= *hi)
            lo++;
        else
            lo = --hi;
    }

    double findMedian() {
        return (*lo + *hi) * 0.5;
    }
};
